// 山洞里有 M 株不同的草药，采每一株都需要一些时间 t_i，每一株也有它自身的价值 v_i。
// 给你一段时间 T，在这段时间里，你可以采到一些草药。让采到的草药的总价值最大。

#include <stdio.h>
#include <stdlib.h>

#define M 45
#define T 81
int tcost[] = {1,2,3,5,3,1,2,3,5,3,1,2,3,5,3,1,2,3,5,3,1,2,3,5,3,1,2,3,5,3,1,2,3,5,3,1,2,3,5,3,1,2,3,5,3};
int values[] = {1,2,3,4,9,1,2,3,4,9,1,2,3,4,9,1,2,3,4,9,1,2,3,4,9,1,2,3,4,9,1,2,3,4,9,1,2,3,4,9,1,2,3,4,9};

// 记录状态，防止重复访问
int dp[M+1][T+1];
int max_v = 0;

void dfs(int pos,int tleft,int v){
    // 状态判断
    if(dp[pos][tleft] != -1){
        return;
    }

    // 判断是否走完,比较结果
    if(pos==M){
        if(tleft < tcost[pos-1] || v + values[pos-1] <= max_v){
            return;
        }else{
            max_v = v + values[pos-1];
            return;
        }
    }

    // 向下递归
    if(tleft >= tcost[pos-1]){
        dfs(pos+1,tleft-tcost[pos-1],v + values[pos-1]);
    }
    dfs(pos+1,tleft,v);
    
    // 记录状态
    dp[pos][tleft] = 0;
    
} 

int main(){
    // 初始化dp
    for(int i=1;i<=M;i++){
        for(int j=1;j<=T;j++){
            dp[i][j] = -1;
        }
    }

    dfs(1,T,0);
    printf("%d",max_v);

    return 0;
}